// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii/description
// https://www.jiuzhang.com/problem/best-time-to-buy-and-sell-stock-iii/  这个讲得很好
class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        int k = 2;
        vector<vector<int>> rec(k + 1, vector<int>(n, 0));
        for (int i = 1; i < k + 1; ++i) {
            int maxDiff = -prices[0]; 
            for (int j = 1; j < n; ++j) {
                // rec[i][j] = rec[i][j - 1];
                // // 如果卖出股票，设是在第m天买入，那么第j天的最大利润就是两天的价格差+最多交易i-1次时第m天的获利。这里的m需要从0遍历到j-1。
                // for (int m = 0; m < j; ++m) // TLE
                //     rec[i][j] = max(rec[i][j], prices[j] - prices[m] + rec[i - 1][m]);

                // 为节省这部分的时间开销，用maxDiff表示：最多交易i-1次时，从第0天到第j-1天最大利润-当天价格的最大值。
                maxDiff = max(maxDiff, rec[i - 1][j - 1] - prices[j - 1]);
                rec[i][j] = max(rec[i][j - 1], prices[j] + maxDiff);
            } 
        }
        return rec[k][n - 1];
    }
    
    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/
    // 法二：
    // int maxProfit(vector<int> &prices) {
    //     int buy1 = INT_MIN, buy2 = INT_MIN;
    //     int sell1 = 0, sell2 = 0;
    //     for (int price: prices)
    //     {
    //         buy1 = max(buy1, -price);
    //         sell1 = max(sell1, buy1 + price);
    //         buy2 = max(buy2, sell1 - price);
    //         sell2 = max(sell2, buy2 + price);
    //     }
    //     return sell2;
    // }
};